package leecode

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	stack := make([]int, 0)
	result := make([]int, len(nums1))
	for i := range result {
		result[i] = -1
	}
	hashMap := make(map[int]int) //key为数组中的元素 , value为该元素对应的下标
	for index, value := range nums1 {
		hashMap[value] = index
	}
	stack = append(stack, 0) //初始化栈顶的元素
	for i := 1; i < len(nums2); i++ {
		//拿到栈顶的元素
		topIndex := stack[len(stack)-1]
		//如果当前元素大于栈顶元素
		if nums2[i] > nums2[topIndex] {
			//检测当前元素是否存在于栈顶
			for len(stack) != 0 && nums2[i] > nums2[topIndex] {
				if index, ok := hashMap[nums2[topIndex]]; ok {
					result[index] = nums2[i]
				}
				//将栈顶元素弹出
				stack = stack[:len(stack)-1]
				if len(stack) != 0 {
					topIndex = stack[len(stack)-1]
				}
			}
			stack = append(stack, i)
		} else {
			stack = append(stack, i)
		}
	}
	return result
}
